#include "LinkList.h"
#include "stdlib.h"
#include "math.h" 



/******************************************************************************
*函数名称：  ListManageInit
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数  
*输出参数：  无
*返回值  ：  无
*功能描述：  初始化链表管理器 
*调用方法：  初始化链表管理器，并把数量保存为0 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
void ListManageInit (ListManage *listManage) {

  listManage->head = NULL;		//管理器头指针和尾指针都NULL 
  listManage->tail = NULL;
  listManage->Length = 0;		//链表元素个数为0 
}

/******************************************************************************
*函数名称：  ListLength
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数  
*输出参数：  无
*返回值  ：  无
*功能描述：  获取链表长度 
*调用方法：  获取链表长度 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
long ListLength (ListManage *listManage) {
  return (listManage->Length);
}


/******************************************************************************
*函数名称：  ListPeekHead
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数  
*输出参数：  无
*返回值  ：  链表头节点指针 。为空，说明 链表无节点 
*功能描述：  获取第头节点，如果为空，则说明链表无节点，也可以用于判断链表状态 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekHead (ListManage *listManage) {
  return (listManage->head);
}

/******************************************************************************
*函数名称：  ListPeekTail
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
*输出参数：  无
*返回值  ：  链表尾节点指针 。为空，说明 链表无节点 
*功能描述：  获取一个尾节点，如果为空，则说明链表无节点，也可以用于判断链表状态 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekTail (ListManage *listManage) {
  return (listManage->tail);
}


/******************************************************************************
*函数名称：  ListPeekNext
*输入参数：  listNode，输入当前节点，用于获取此节点的后续节点 
*输出参数：  无
*返回值  ：  输入节点的后一个节点 。 
*功能描述：  获取当前节点的后一个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekNext (ListNode *listNode) {
  return (listNode->next);
}


/******************************************************************************
*函数名称：  ListPeekPrev
*输入参数：  listNode，输入当前节点，用于获取此节点的前一个节点 
*输出参数：  无
*返回值  ：  输入节点的前一个节点 。 
*功能描述：  获取当前节点的后一个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekPrev (ListNode *listNode) {
  return (listNode->prev);
}

/******************************************************************************
*函数名称：  ListPeekItem
*输入参数：  listManage,链表管理器 
**			 listNode，输入当前节点，用于获取此节点的后续节点 
*输出参数：  无
*返回值  ：  返回对应节点在链表中的位置，如果是-1表明没有在链表里边 
*功能描述：  根据节点指针获取节点所在的索引位置 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
long ListPeekItem (ListManage *listManage, ListNode *listNode) { 
  #if 0  //从头到尾搜索，效率差 
  long index = -1;
  long i = 0;
  ListNode *pln;
  for (pln = ListPeekHead(listManage); pln != NULL; pln = ListPeekNext(pln)) {  		
  		if(pln == listNode) {
  			index = i;
			break;	
		}
  		i++;
  }
  #else  //从头尾往中间逼近搜索 
  long index = -1;
  long i;
  const long halflength = (listManage->Length + 1) / 2; 	//计算链表一半长度 
  ListNode *plnh,*plnt; //头尾节点指针 
  plnh = ListPeekHead(listManage);	//获取头节点 
  plnt = ListPeekTail(listManage);	//获取尾节点 
  for(i = 0; i < halflength; i++)
  {
  		//如果从前往后索引找到数据 
  		if(plnh == listNode) {
  			index = i;
			break;	
		}
		//如果从后往前找到数据 
		if(plnt == listNode) {
  			index = listManage->Length - i - 1;
			break;	
		}
		plnh = ListPeekNext(plnh);//头节点指向下一个 
		plnt = ListPeekPrev(plnt);//尾节点指向上一个 
  }
  
  #endif
  //最快的搜索方法是递归对半搜索，可以尝试编写 
  
  return (index);
}

/******************************************************************************
*函数名称：  ListPeekIndex
*输入参数：  listManage,链表管理器 
**			 index,获取节点的索引，如果是负数，表明是从后往前搜索，
**			       最后一个数据索引是-1，以此类推 
*输出参数：  无
*返回值  ：  返回对应节点指针，如果为NULL表明没有对应节点 
*功能描述：  获取当前节点的后一个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekIndex (ListManage *listManage, long index) {
  
  long i = 0;
  ListNode *pln = ListPeekHead(listManage);
  //如果链表为空，则退出 
  if(pln == NULL) {
  	return NULL;
  }
  //如果索引大于链表总长度，则退出 
  if(index >=  listManage->Length) {		//正数大于链表长度 
  	return NULL;
  } else if(index < -listManage->Length) {	//负数小于链表长度的相反数 
  	return NULL;
  }
  
  if(index >= 0 ) {
  	pln = ListPeekHead(listManage);			//正数从前到后搜索 
  	for(i = 0; i < index; i++) {
	  	pln = ListPeekNext(pln);
	}
  } else {
  	pln = ListPeekTail(listManage);			//负数从后到前搜索 
  	for(i = -1; i > index; i--) {
	  	pln = ListPeekPrev(pln);
	}
  }
   
  return (pln);
}

/******************************************************************************
*函数名称：  ListPutTail
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
*			 listNode 将要添加的节点地址 
*输出参数：  无
*返回值  ：  无
*功能描述：  把新节点追加到链表最后 
*调用方法：  插入节点时使用 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
void ListPutTail (ListManage *listManage, ListNode *listNode) {
  //如果新节点已经存在，则不做任何动作 
  if(ListPeekItem(listManage, listNode) >= 0) 
  	return;
	
  listNode->prev = listManage->tail;		//新节点上一个元素指向原链表尾指针 
  listNode->next = NULL;

  if (listManage->tail == NULL) {    		//如果头指针为空，表明原链表无数据，
    listManage->head = listNode;			//新节点成为链表的头 
  }
  else {
    listManage->tail->next = listNode;		//否则，就把原链表的尾元素的下一个链接到新节点上 
  }

  listManage->tail = listNode;				//之后把链表管理器的尾指针指向新元素 
  listManage->Length++; 
}

/******************************************************************************
*函数名称：  ListPutHead
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
*			 listNode 将要添加的节点指针
*输出参数：  无
*返回值  ：  无
*功能描述：  把新节点追加到链表最开始，多用于栈链表 
*调用方法：  插入节点时使用 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
void ListPutHead (ListManage *listManage, ListNode *listNode) {
  //如果新节点已经存在，则不做任何动作 
  if(ListPeekItem(listManage, listNode) >= 0) 
  	return;
  
  listNode->prev = NULL;
  listNode->next = listManage->head;		//注释参考上一个函数 

  if (listManage->head == NULL) {
    /* List empty, add tail */
    listManage->tail = listNode;
  }
  else {
    listManage->head->prev = listNode;
  }

  listManage->head = listNode;
  listManage->Length++;

}


/******************************************************************************
*函数名称：  ListInsertBefor
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把节点lnew插入到 listNode之前 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertBeforItem (ListManage *listManage, ListNode *listNode, ListNode *lnew) {
  //如果新节点已经存在，则不做任何动作 
  if(ListPeekItem(listManage, lnew) >= 0) 
  	return;
  //如果已知节点不在链表里，退出 
  if(ListPeekItem(listManage, listNode) < 0) 
  	return;
  
  lnew->next = listNode;
  lnew->prev = listNode->prev;

  if (listNode->prev == NULL) {
    listManage->head = lnew;
  }
  else {
    listNode->prev->next = lnew;
  }

  listNode->prev = lnew;
  listManage->Length++; 
}

/******************************************************************************
*函数名称：  ListInsertAfter
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把节点lnew插入到 listNode之后 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertAfterItem (ListManage *listManage, ListNode *listNode, ListNode *lnew) {
  //如果新节点已经存在，则不做任何动作 
  if(ListPeekItem(listManage, lnew) >= 0) 
  	return;
  //如果已知节点不在链表里，退出 
  if(ListPeekItem(listManage, listNode) < 0) 
  	return;
  
  lnew->next = listNode->next;
  lnew->prev = listNode;

  if (listNode->next == NULL) {    
    listManage->tail = lnew;
  }
  else {
    listNode->next->prev = lnew;
  }

  listNode->next = lnew;
  listManage->Length++; 
}

/******************************************************************************
*函数名称：  ListInsertBeforIndex
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无  
*功能描述：  把节点lnew插入到 listNode之前 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertBeforIndex (ListManage *listManage, long index, ListNode *lnew) {
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew) >= 0) 
		return;
  	
	ListNode *listNode = ListPeekIndex(listManage, index);
	if(listNode != NULL)
		ListInsertBeforItem(listManage, listNode, lnew);
}

/******************************************************************************
*函数名称：  ListInsertAfterIndex
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把节点lnew插入到 listNode之前 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertAfterIndex (ListManage *listManage, long index, ListNode *lnew) {
	//如果新节点已经存在，则不做任何动作 
	if(ListPeekItem(listManage, lnew) >= 0) 
		return;
		
	ListNode *listNode = ListPeekIndex(listManage, index); //获取索引对应的节点指针 
	if(listNode != NULL)
		ListInsertAfterItem(listManage, listNode, lnew);
}

/******************************************************************************
*函数名称：  ListPopHead
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
*输出参数：  无
*返回值  ：  链表第一个节点指针 
*功能描述：  获取第一个节点，并删除 
*调用方法：  弹出后，注意释放内存 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
ListNode *ListPopHead (ListManage *listManage) {
  ListNode *listNode;

  listNode = listManage->head;

  if (listNode != NULL) {
    listManage->head = listNode->next;

    if (listNode->next == NULL) {
      /* List empty, clear tail */
      listManage->tail = NULL;
    }
    else {
      listNode->next->prev = NULL;
    }
  }
  listManage->Length--; 
  return (listNode);
}

/******************************************************************************
*函数名称：  ListPopEnd
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
*输出参数：  无
*返回值  ：  链表的最后一个节点指针 
*功能描述：  弹出最后一个节点 ，并删除 
*调用方法：  弹出后，注意释放内存 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPopEnd (ListManage *listManage) {
  ListNode *listNode;

  listNode = listManage->tail;

  if (listNode != NULL) {
    listManage->tail = listNode->prev;

    if (listNode->prev == NULL) {
      /* List empty, clear tail */
      listManage->head = NULL;
    }
    else {
      listNode->prev->next = NULL;
    }
  }
  listManage->Length--; 
  return (listNode);
}


/******************************************************************************
*函数名称：  ListRemoveItem
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
**			 listNode，将要删除的节点指针
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把listNode从链表中删除 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListRemoveItem (ListManage *listManage, ListNode *listNode) {

  if (listNode->next == NULL) {
    /* Last listNode in listManage */
    listManage->tail = listNode->prev;
  }
  else {
    listNode->next->prev = listNode->prev;
  }

  if (listNode->prev == NULL) {
    /* First listNode in listManage */
    listManage->head = listNode->next;
  }
  else {
    listNode->prev->next = listNode->next;
  }
  listManage->Length--; 
}

/******************************************************************************
*函数名称：  ListPopIndex
*输入参数：  listManage，链表管理器，保存链表的头尾地址和总数 
**			 index,将要被弹出的节点索引 
*输出参数：  无
*返回值  ：  弹出的节点指针。 
*功能描述：  获取index位置的节点，并删除 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPopIndex (ListManage *listManage, long index) {
  ListNode *listNode = ListPeekIndex(listManage, index); 
  ListRemoveItem(listManage, listNode);
  return listNode;
}

/******************************************************************************
*函数名称：  ListSwitchItems
*输入参数：  node1,node2，将要交换的两个节点 
*输出参数：  无
*返回值  ：  无。 
*功能描述：  交换两个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListSwitchItems (ListManage *listManage, ListNode *node1, ListNode *node2) {
	ListNode lspnode;				//用于保存其中一个节点的信息，用于交换 
	  
	if(node1->next == node2){
		//先交换两个节点相邻的两个节点的值 
		if(node1->prev != NULL)
			node1->prev->next = node2;
		if(node2->next != NULL)	
			node2->next->prev = node1;
		node1->next = node2->next;		
		node2->next = node1;
		node2->prev = node1->prev; 
		node1->prev = node2;
	} else if(node2->next == node1){
		if(node2->prev != NULL)
			node2->prev->next = node1;
		if(node1->next != NULL)	
			node1->next->prev = node2;
		node2->next = node1->next;		
		node1->next = node2;
		node1->prev = node2->prev;
		node2->prev = node1;
	} else {
		//先交换两个节点相邻的四个节点的值 
		if(node1->prev != NULL)
			node1->prev->next = node2;
		if(node1->next != NULL)	
			node1->next->prev = node2;
		if(node2->prev != NULL)
			node2->prev->next = node1;
		if(node2->next != NULL)	
			node2->next->prev = node1;
		//再交换两个节点的数据	
		lspnode.next = node1->next;
		lspnode.prev = node1->prev;
		node1->next = node2->next;
		node1->prev = node2->prev;
		node2->next = lspnode.next;
		node2->prev = lspnode.prev;
	}   
	
	if(node1->next == NULL) {
		listManage->tail = node1;
	} else if(node2->next == NULL) {
		listManage->tail = node2;
	}
	
	if(node1->prev == NULL) {
		listManage->head = node1;
	} else if(node2->prev == NULL) {
		listManage->head = node2;
	}
	
}

/******************************************************************************
*函数名称：  ListSwitchIndex
*输入参数：  index1,index2,交换的两个索引位置 
*输出参数：  无
*返回值  ：  无。 
*功能描述：  交换两个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListSwitchIndex (ListManage *listManage, long index1,long index2) {
	ListNode *node1 = ListPeekIndex(listManage, index1);
	ListNode *node2 = ListPeekIndex(listManage, index2);
	
	if((node1 == NULL) || (node2 == NULL)) {
		return;
	}
	ListSwitchItems(listManage, node1, node2);
}

/******************************************************************************
*函数名称：  ListSort
*输入参数：  listManage，链表管理器
*			 s2b,从小到大排列，TRUE为从小到大，FALSE为从大到小 
*			 fun_compare，返回比较值的函数指针，可以是正数，负数，0 
*输出参数：  无
*返回值  ：  无。 
*功能描述：  按照 fun_compare的规则排序链表 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.12.3
******************************************************************************/
void ListSort(ListManage *listManage,BOOL s2b, FUN_COMPARE fun_compare) {
	ListNode *pNode = ListPeekHead(listManage); 		//前节点
	ListNode *tNode = ListPeekNext(pNode);				//后节点
	ListNode *mNode ;							//暂存节点
	char comp;
	
	//使用选择排序方法进行排序 
	//算法原理参考视频1:31位置  https://b23.tv/bYDnA2N
	while(tNode != NULL) {
		while(tNode != NULL) {
			comp = fun_compare(pNode, tNode) ;
			if(!s2b)  
				comp = -comp;
			if(comp > 0) {
				//链表位置交换 
				ListSwitchItems(listManage, pNode, tNode);
				//判断节点的交换 
				mNode = pNode;
				pNode = tNode;
				tNode = mNode;
			}
			tNode = ListPeekNext(tNode);
		}
		pNode = ListPeekNext(pNode);
		tNode = ListPeekNext(pNode);			
	} 
	  
}

